package com.xy6.algo.dynamic;


/**
 * 矩阵连乘问题
 * 
 * <pre>
 * 给定n个矩阵：A1,A2,...,An，其中Ai与Ai+1是可乘的，i=1，2...，n-1。
 * 确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。
 * 输入数据为矩阵个数和每个矩阵规模，输出结果为计算矩阵连乘积的计算次序和最少数乘次数。
 * 
 * 解决问题的关键在于考虑到：计算Ai * A(i+1) * ... * Aj时，假设矩阵在Ak与A(k+1)之间断开，
 * k范围为[i,j]，k在每个位置时，表达式值为Sk，则min(Sk)即为最少的连乘次数。
 * Sk = (Ai * A(i+1) * ... * Ak) * (A(k+1) * ... * Aj)
 * 状态转移方程为：
 * 如果i = j, 则m[i,j] = 0；
 * 如果i < j，则m[i,j] = min(m[i,k] + min[k+1,j] + P(i-1) * Pk * Pj)，k范围为[i,j]
 * </pre>
 * 
 * @author zhang
 * @since 2017-11-25
 */
public class MatrixChain {

	public static void main(String[] args) {
		int[] p = new int[] { 100, 5, 50 };
		int result = calc(p);
		System.out.println(result);
	}
	
	public static int calc(int[] p){
		int n = p.length - 1;
		int[][] m = new int[n + 1][n + 1];

		// 计算当前矩阵i与后面一个矩阵(i+1)乘积
		for(int i=1; i<=n-1; i++){
			m[i][i + 1] = p[i - 1] * p[i] * p[i + 1];
		}
		
		int min = 0;
		int temp = 0;
		for (int i = n - 1; i >= 1; i--) {
			for (int j = i + 1; j <= n; j++) {
				min = 0;
				for (int k = i; k <= j - 1; k++) {
					temp = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
					if(min == 0){
						min = temp;
					} else {
						min = temp < min ? temp : min;
					}
				}
				m[i][j] = min;
			}
		}
		return m[1][n];
	}

}
